1930E - 234 Wonderful Wonderful - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=998244353,N=1e6+100,maxn=1e6;
int fl[N],nf[N];

int mi(int x,int t){
	int d=1;
	while(t){
		if(t%2) d=(ll)d*x%mod;
		x=(ll)x*x%mod;t/=2;
	}
	return d;
}
int ni(int x) {return mi(x,mod-2);}

int C(int n,int m){
	if(m<0||m>n) return 0;
	return (ll)fl[n]*nf[m]%mod*nf[n-m]%mod;
}

int main()
{
	
	fl[0]=1;for(int i=1;i<=maxn;i++) fl[i]=(ll)fl[i-1]*i%mod;
	nf[maxn]=ni(fl[maxn]);for(int i=maxn-1;i>=0;i--) nf[i]=(ll)nf[i+1]*(i+1)%mod;
	
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		
		for(int i=1;i<=(n-1)/2;i++){
			int Sum=1;
			for(int j=i*2;j<=n;j+=i*2)
				Sum=(Sum+C(n,j))%mod;
				
			for(int len=2;len<=n;len=len+i*2) Sum=(Sum-C(n-len+1,2*(i-1)+1)+mod)%mod;
			/*for(int j=1;j<=n;j++)
				for(int k=j;k<=n;k++)
					if((k-j+1+(i-1)*2)%(i*2)==0){
						int tmp=(ll)C(j-1,i-1)*C(n-k,i-1)%mod;
						C(j-1,j-i) n-k,i-1
						n-k+j-1,j-1
						n-len
						Sum=(Sum-tmp+mod)%mod;
					}*/
			printf("%d ",Sum);
		}
		printf("\n");
	}
	
	return 0;
}